package algorithm;

/**
 * create by yongli on 2020-08-20 11:27
 */

public class MergeLinkedList {
    public MyNode merge(MyNode head1,MyNode head2){
        if(head1 == null && head2== null){
            return null;
        }
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        MyNode head;
        if(head1.data < head2.data){
            head = new MyNode(head1.data);
            head1 = head1.next;
        }else {
            head = new MyNode(head2.data);
            head2 = head2.next;
        }
        MyNode tail =head;
        while (head1 != null && head2 != null){
            MyNode node;
            if(head1.data < head2.data){
                node = new MyNode(head1.data);
                head1 = head1.next;

            }else {
                node = new MyNode(head2.data);
                head2 = head2.next;
            }
            tail.next = node;
            tail = tail.next;
        }
        if(head1 == null){
            while (head2 != null){
                MyNode node = new MyNode(head2.data);
                tail.next = node;
                tail = tail.next;
                head2= head2.next;
            }
        }
        if(head2 == null){
            while (head1 != null){
                MyNode node = new MyNode(head1.data);
                tail.next = node;
                tail = tail.next;
                head1= head1.next;
            }
        }
        return head;

    }
}

class MyNode {
    int data;
    MyNode next;

    public MyNode(int data){
        this.data =data;
        next = null;
    }
}
